package com.situ.linkedlist;

import com.sun.swing.internal.plaf.metal.resources.metal_zh_TW;

public class HHLinkedList {

	// 头节点
	private Node head;

	// 尾节点
	private Node tail;

	// 当前元素数量
	private int size;


	// 1、追加到最后
	// append(Object o)
	public boolean append(Object element) {
		// 根据数据，创建节点
		Node newNode = new Node();
		newNode.setData(element);

		// 找最后一个节点
		// 空链表
		if (head == null) {
			head = newNode;
		}else {
			// 不是空链表

			/*
			// 从头节点一直往下找
			
			Node tail = head;
			
			// 遇空指针域，则代表遇到最后一个节点
			while(tail.getNext() !=null) {
				tail = tail.getNext();
			}
			*/
			
			// 将新节点添加到尾结点后边
			tail.setNext(newNode);
		}
		// 记住新尾节点
		tail = newNode;
		// 大小加1
		size++;
		return true;
	}

	// 2、插入到指定下标
	public boolean insert(int index, Object element) {
		if (checkIndex(index) == false) {
			return false;
		}

		// 给元素创建新节点
		Node newNode = new Node();
		newNode.setData(element);

		// 有效index就插入到指定的位置
		if (index == 0) {
			newNode.setNext(head);
			head = newNode;
		} else {
			// 找到index-1的位置
			Node cur = head;
			for (int i = 0; i < index - 1; i++) {
				cur = cur.getNext();
			}
			newNode.setNext(cur.getNext());
			cur.setNext(newNode);
		}

		// 大小加1
		size++;
		return true;
	}

	// 3、删除指定位置的元素，并返回被删除的元素，删除失败时返回空
	public Object remove(int index) {
		if (checkIndex(index) == false) {
			return null;
		}

		if (index == 0) {
			Node removeNode = head;
			head = head.getNext();

			if (head == null) {
				tail = null;
			}
			// 大小减1
			// 删除的逻辑就是删除成功才减，所以不把自减挪上去
			size--;
			return removeNode;
		} else {
			// 找到index-1的位置
			Node cur = head;
			for (int i = 0; i < index - 1; i++) {
				cur = cur.getNext();
			}
			Node removeNode = cur.getNext();
			cur.setNext(removeNode.getNext());
			// 如果删除的是尾部元素
			if (cur.getNext() == null) {
				tail = cur;
			}
			// 大小减1
			size--;
			return removeNode;
		}
	}

	// 4、清空全部元素
	public void clear() {
		head = null;
		tail = null;
	}

	// 5、根据下标获取元素
	public Object get(int index) {
		if (checkIndex(index) == false) {
			return null;
		}

		// 找到index的位置
		Node cur = head;
		for (int i = 0; i < index; i++) {
			cur = cur.getNext();
		}

		return cur.getData();
	}

	// 检查下标有效性
	public boolean checkIndex(int index) {
		// 判断index是不是一个有效index（ >0 & <size）
		return index >= 0 && index < size;
	}
	/**
	 * 内部类 定义节点类型
	 */
	public static class Node {
		private Object data;
		private Node next;

		public Object getData() {
			return data;
		}

		public void setData(Object data) {
			this.data = data;
		}

		public Node getNext() {
			return next;
		}

		public void setNext(Node next) {
			this.next = next;
		}

	}
}
